package leetcode;

import java.util.Stack;

/**
 * @author Liangyaoyun
 */
public class leetCode5 {
    //动态规划解法
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        int maxLen = 1;
        int index = 0;
        //单个字符没必要判断,所以一开始判断的字符串长度应该设为2
        for (int Length = 2; Length <= len; Length++) {
            for (int i = 0; i < len; i++) {
                int j = Length + i - 1;
                //判断j是否越界
                if (j >= len) {
                    break;
                }
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    //如果字符串长度小于三直接赋予真值
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]&&j-i+1>maxLen){
                    maxLen=j-i+1;
                    index=i;
                }
            }
        }
        return s.substring(index,maxLen+index);
    }
}
